package 中等.前缀和与差分;

import java.util.Map;
import java.util.TreeMap;

/**
 * 实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
 * 当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订。
 * 事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为  startTime <= x < endTime。
 * 实现 MyCalendarTwo 类：
 * <p>
 * MyCalendarTwo() 初始化日历对象。
 * boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
 *
 * @ https://leetcode.cn/problems/my-calendar-ii/description/?envType=daily-question&envId=2025-01-03
 * @date 2025/01/05
 */
public class 我的日程安排表II_731 {

    public static void main(String[] args) {

        MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
        myCalendarTwo.book(10, 20);
        myCalendarTwo.book(50, 60);
        myCalendarTwo.book(10, 40);
        myCalendarTwo.book(5, 15);
        myCalendarTwo.book(5, 10);
        myCalendarTwo.book(25, 55);

    }

    /**
     * 差分数组
     * 每次预定将[start,end)的区间+1
     * 由于[start,end)范围过大，使用TreeMap模拟差分数组
     */
    static class MyCalendarTwo {

        private TreeMap<Integer, Integer> treeMap = new TreeMap<>((a, b) -> a - b);

        public MyCalendarTwo() {

        }

        // 不包含 endTime
        public boolean book(int startTime, int endTime) {
            treeMap.put(startTime, treeMap.getOrDefault(startTime, 0) + 1);
            treeMap.put(endTime, treeMap.getOrDefault(endTime, 0) - 1);
            int curNum = 0;

            for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {

                Integer freq = entry.getValue();
                curNum += freq;

                if (curNum > 2) {
                    // 要还原，预定不了
                    treeMap.put(startTime, treeMap.getOrDefault(startTime, 0) - 1);
                    treeMap.put(endTime, treeMap.getOrDefault(endTime, 0) + 1);
                    return false;
                }
            }
            return true;
        }
    }

}
